#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        vector<int> forwardMax(height.size()), backwardMax(height.size());
        forwardMax[0] = height[0];
        backwardMax[height.size() - 1] = height[height.size() - 1];
        for (int i = 1; i < height.size(); i++)
        {
            forwardMax[i] = max(forwardMax[i - 1], height[i]);
        }
        for (int i = height.size() - 2; i >= 0; i--)
        {
            backwardMax[i] = max(backwardMax[i + 1], height[i]);
        }
        int sum = 0;
        for (int i = 0; i < height.size(); i++)
        {
            sum += min(forwardMax[i], backwardMax[i]) - height[i];
        }
        return sum;
    }
};

int main()
{
    cout << "Code42" << endl;
    Solution s;
    vector<int> height{4, 2, 0, 3, 2, 5};
    cout << s.trap(height) << endl;
    return 0;
}